import com.kiwi.nixu.common.LNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目描述：给定两个单链表，链表的每个结点代表一位数，计算两个数的和。例如，输入链表（3→1→5）和链表（5→9→2），
 * 输出：8→0→8，即513+295=808，注意个位数在链表头
 */
public class C如何计算两个单链表所代表的数之和 {

    /**
     * 方法
     *
     * 方法一：整数相加法主要思路为：分别遍历两个链表，求出两个链表所代表的整数的值，
     * 然后把这两个整数进行相加，最后把它们的和用链表的形式表示出来。这种方法的优点是计算简单，
     * 但是有个非常大的缺点：当链表所代表的数很大时（超出了long int的表示范围），就无法使用这种方法了。
     *
     * 方法二：链表相加法主要思路为：对链表中的结点直接进行相加操作，
     * 把相加的和存储到新的链表中对应的结点中，同时还要记录结点相加后的进位，
     * 如下图所示。[插图]使用这种方法需要注意如下几个问题：
     * ①每组结点进行相加后需要记录其是否有进位；
     * ②如果两个链表H1与H2的长度不同（长度分别为L1和L2，且L1＜L2），当对链表的第L1位计算完成后，接下来只需要考虑链表L2剩余的结点的值（需要考虑进位）；
     * ③对链表所有结点都完成计算后，还需要考虑此时是否还有进位，如果有进位，则需要增加新的结点，此结点的数据域为1
     */

    /**
     * 方法功能：对两个带头结点的单链表所代表的的数相加
     * 输入参数，h1:第一个链表头结点；h2：第二个链表头结点
     * 返回值：相加后链表的头结点
     */
    public static LNode add(LNode h1, LNode h2) {
        if (h1 == null || h1.next == null) {
            return h2;
        }
        if (h2 == null || h2.next == null) {
            return h1;
        }
        int c = 0;//用来记录进位
        int sum = 0;//用来记录两个结点相加的值
        LNode p1 = h1.next;//用来遍历h1
        LNode p2 = h2.next;//用来遍历h2
        LNode tmp = null;//用来指向新创建的存储相加和的节点
        LNode resultHead = new LNode();//相加后链表头结点
        resultHead.next = null;
        LNode p = resultHead;//用来指向链表resultHead最后一个节点
        while (p1 != null && p2 != null) {
            tmp = new LNode();
            tmp.next = null;
            sum = p1.data + p2.data + c;
            tmp.data = sum % 10;
            c = sum / 10;
            p = tmp;
            p1 = p1.next;
            p2 = p2.next;
        }
        //链表h2比h1长，接下来只需要考虑h2剩余节点的值
        if (p1 == null) {
            while (p2 != null) {
                tmp = new LNode();
                tmp.next = null;
                sum = p2.data + c;
                tmp.data = sum % 10;
                c = sum / 10;
                p.next = tmp;
                p = tmp;
                p2 = p2.next;
            }
        }
        //链表h1比h2长，接下来只需要考虑h1剩余节点的值
        if (p2 == null) {
            while (p1 != null) {
                tmp = new LNode();
                tmp.next = null;
                sum = p1.data + c;
                tmp.data = sum % 10;
                c = sum / 10;
                p.next = tmp;
                p = tmp;
                p1 = p1.next;
            }
        }
        //如果计算完成后还有进位，则增加新的节点
        if (c == 1) {
            tmp = new LNode();
            tmp.next = null;
            tmp.data = 1;
            p.next = tmp;
        }
        return resultHead;
    }

    public static void main(String[] args) {
        int i = 1;
        LNode head1 = new LNode();
        head1.next = null;

        LNode head2 = new LNode();
        head2.next = null;

        LNode tmp = null;
        LNode cur = head1;
        LNode addResult = null;

        //构造第一个链表 开始
        for (; i < 7; i++) {
            tmp = new LNode();
            tmp.data = i + 2;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        //构造第一个链表 结束

        //构造第二个链表
        cur = head2;
        for (i = 9; i > 4; i--) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        System.out.print("Head1: ");
        for (cur = head1.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + " ");
        }
        System.out.print("\nHead2: ");
        for (cur = head2.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + " ");
        }
        addResult = add(head1, head2);
        System.out.print("\n相加后");
        for (cur = addResult.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + " ");
        }
    }
}